The present invention relates generally to content addressable memories (CAMs) and more particularly to CAMs having precharge and evaluation cycles.
Due to the increasing importance of data networks, including the Internet, the prevalence of content addressable memories (CAMs) has continued to proliferate. CAMs, also referred to as xe2x80x9cassociative memories,xe2x80x9d can provide rapid matching functions that are often needed in certain packet processing hardware devices, such as routers and network switches, to name just two. In a typical packet processing operation, a device can receive a packet. The packet can include a xe2x80x9cheaderxe2x80x9d that includes various data fields that indicate how the packet should be processed. The device can use a matching function, provided by a CAM, to compare one or more header fields to xe2x80x9clook-upxe2x80x9d tables stored in the CAMs.
As just one example, a router can use a matching function to match the destination of an incoming packet with a xe2x80x9cforwardingxe2x80x9d table. The forwarding table can provide xe2x80x9cnexthopxe2x80x9d information that can allow the incoming packet to be transmitted to its final destination, or to another node on the way to its final destination.
The look-up tables in packet processing devices (which are typically stored in a CAM) are rarely static. That is, the entries with such a table may be constantly updated with different information. This may be particularly true in routers, which can update forwarding tables thousands of times a second.
A typical CAM can store the data values of a look-up table in one or more CAM cell arrays. The CAM cell arrays can be configured into a number of entries, each of which can provide a match indication. In a compare (i.e., match) operation, the data values stored within the entries can be compared to a comparand value (also referred to as a xe2x80x9csearch keyxe2x80x9d). In a typical packet processing device, the comparand value can include a field extracted from a data packet header. If a data value matches an applied comparand value, the corresponding entry can generate an active match indication. If a data value does not match an applied comparand value, the corresponding entry can generate an inactive match indication (signifying a xe2x80x9cmismatchxe2x80x9d) condition.
To better understand various aspects of the present invention, a conventional example will now be described.
FIG. 1A is a conventional example that shows the relation between the applied comparand values and the match circuitry and is indicated by the general reference character 100. Comparand drivers 102 and 104 are enabled by a CDEN signal. The illustrated data value cell 106, upon comparison to the applied comparand values, CD and CD_, through NMOS devices 108 and 110, respectively, supplies the bit match indicator signals, such as MATCHO_ 120-0 for the illustrated bit position. All bit match indicator signals 120-0 through 120-n for an entry are coupled to the gates of the corresponding NMOS devices 114-0 through 114-n, A low on a bit match indicator signal conveys a match to the applied comparand and a high indicates a mismatch for the given bit position. Because the preferred embodiment is a full ternary CAM, each bit position can also be individually masked. This is accomplished with the devices 112-0 through 112-n, where the gate of each device can be coupled to the corresponding mask bit signal 118-0 through 118-n. The match detection circuitry also includes precharge control circuitry 116 that pulls the MATCH LINE to a high level during a precharge state.
FIG. 1B shows a corresponding timing diagram that illustrates the xe2x80x9cPRECHxe2x80x9d (precharge) and xe2x80x9cEVALxe2x80x9d (evaluation) cycles of the match circuitry. During the precharge phase, the MATCH LINE is pulled to a high-level, but not necessarily to the full VDD level by the precharge circuitry 116 that is enabled by the PRCH_ signal activating low. To facilitate match evaluation, the MATCH0_ to MATCHn_ signals 120-0 through 120-n should be settled to their appropriate levels based on the applied comparand values when the EVAL period begins. In the example illustrated, both CD and CD_ are fully discharged while CDEN is low. The EVAL stage begins when CDEN is charged high and the global comparand values, CDG and CDG_ are allowed to propagate their values to the local comparands, CD and CD respectively. At this point, the MATCH0_ to MATCHn_ signals 120-0 through 120-n can settle to indicate the match status of each bit of the entry.
Focusing on the precharge cycle, one approach is to discharge both CD and CD_ completely to ground while precharging the MATCH LINE to a high level. This high level can be an intermediate level and it does not have to be the full VDD level. The MASK0 to MASKn values 118-0 through 118-n, because they are direct outputs from static storage cells, are at full supply rail levels. In one approach, the MATCH0_ to MATCHn_ lines 120-0 through 120-n can follow the local applied comparand lines to full power rail levels. Commonly-owned, co-pending patent application entitled xe2x80x9cContent Addressable Memory Having Compare Data Transition Detectorxe2x80x9d by Eric Voelkel, filed on Jul. 12, 2001, and incorporated herein by reference shows one approach that can equalize comparand lines, both global and local, to an approximate half-VDD level during precharge. This approach can save power in the comparand line switching. However, if such teachings are used in conjunction with some types of match circuitry, such as that shown in FIG. 1A, during the time period when a MATCH LINE is precharging, comparand lines are equalized close to half-VDD. This situation can cause a current path from VDD to ground through the precharge circuitry 116 of FIG. 1 and at least one of the NMOS discharge stacks, 112-0 and 114-0 through 112-n and 114-n.
It would be desirable to arrive at some way of reducing this current that would result from the overlap of any local comparand line at a level greater than an NMOS threshold voltage, which can occur for a mid-VDD level equalization, and the precharging of the MATCH LINE.
According to disclosed embodiments, a content addressable memory (CAM) can include a number of match lines, each coupled to the mask cells and the bit match indication signals that comprise each entry of the ternary CAM. The mask cell values correspond to the data values to implement the ternary storage function. The match indication signals result from comparison of the stored data values to the applied comparands. In order to take advantage of power saving techniques employed in the applied comparand precharging scheme described above, corresponding precharge control can be inserted into the match sense amplifier circuitry.
According to one aspect of the embodiments, a binary CAM can include a common node coupled to the match transistors and also to the discharge control device.
According to another aspect of the embodiments, a CAM can include a common node coupled to the series-coupled mask devices and connection devices. This common node can also be coupled to a discharge control device. The discharge control device can be controlled by the precharge control signal. A match line precharge limiting device can also be included.
According to another aspect of the embodiments, a CAM can include a match indication feedback device coupled in series with the discharge control device. The match indication feedback device can be controlled by the match line amplifier circuit output whereby the common node discharge path is cut-off upon detection of a search miss for that entry.
According to another aspect of the embodiments, a CAM can include a combined equalization and precharge indication signal further logically combined with a match line detection signal. The output of the logical combination can control the common node discharge control device.
According to another aspect of the embodiments, a CAM can include a shared common node between a top and a bottom entry. Precharge limiting circuitry for the common node can also be included. Match indication feedback devices can be coupled to the common node discharge control path wherein one match indication feedback device can be coupled to the top entry and the other match indication feedback device can be coupled to the bottom entry. The common node discharge path can then be cut-off if both the top and the bottom entry are detected as search misses.
An advantage of the disclosed embodiments is that static current paths can be avoided by disallowing the discharge of the common node during the precharge portion of a cycle, thereby saving power.
An advantage of the disclosed embodiments is that the match line precharge level is limited to less than a full power rail level, also resulting in power savings.
An advantage of the disclosed embodiments is that the common node precharge is limited and controlled, also resulting in power savings.
An advantage of the disclosed embodiments is that a logical combination of the equalization and the precharge control signal and the match line detection signal can be used to control the common node discharge path, resulting in simpler overall control circuitry.
An advantage of the disclosed embodiments is that two adjacent entries can share a common node, resulting in layout area savings and power savings.